1. Field of the Invention
The present invention relates to error detection and/or correction codes, and in particular to linear codes of Hamming type.
2. Description of the Related Art
The Hamming code is an error detection and correction code used in many fields. Its use for transmission will be described, in the case where the data to be transmitted are in the form of 16-bit words.
Let X be the word to be transmitted. X can be represented by a vector Xe, the 16 components X0, X1, . . . X15 of which correspond to the 16 bits of the word to be transmitted. Five error detection bits Ci (C0 . . . C4) are obtained by multiplying a parity check matrix H, called a Hamming matrix, of dimensions 5×16, by vector Xe in the form of a column vector.
FIG. 1A illustrates Hamming matrix H for 16 bits and FIG. 1B illustrates how to obtain the detection bits. Calling hij the elements of matrix H, the error detection bits Ci are given by:       C    i    =            ∑              j        =        0            15        ⁢                   ⁢                  h        ij            ·              X        j            Xj being the j-th component of vector Xe.
Upon transmission, 21-bit words, formed of the 16 data bits Xj and of the 5 detection bits Ci are sent. The received word includes 16 bits Xr corresponding to the data bits and 5 bits Cr corresponding to the detection bits. It is possible for Xr and Cr not to be equal to Xj and Ci if errors occur during transmission.
At the reception, a syndrome S with five components S0, . . . S4 is calculated by multiplying a determined matrix H′ of dimensions 5×21 by a column vector with 21 components, including the 16 bits Xr and the 5 received bits Cr.
FIG. 2A illustrates matrix H′. The first 16 columns of matrix H′ correspond to the 16 columns of matrix H. The 5 following columns each include a single “1”. The 17-th column has its “1” on the first line, the 18-th column has its “1” on the second line, and so on until the 21rst column, which has its “1” on the fifth line. The last five columns of matrix H′ are used to determine possible errors in the detection bits.
FIG. 2B illustrates the calculation of syndrome S.
If syndrome S has all its components equal to 0, the transmission occurs with no error and all the bits of the received word, be they data bits or detection bits, are correct.
If S is different from 0, the received word includes one or several errors. If a single bit of the received word is erroneous, the obtained syndrome enables correcting the error. Indeed, the obtained syndrome corresponds in this case to the column having has its elements multiplied by the erroneous bit. Thus, if the calculated syndrome is equal to       S    =          (                                    0                                                0                                                0                                                1                                                1                              )        ,the components (00011) of the syndrome correspond to the elements of the first column of the Hamming matrix, which means that the first bit, X0, is erroneous.
Similarly, if the calculated syndrome is equal to             S      ″        =          (                                    1                                                0                                                0                                                0                                                0                              )        ,and there is a single error in the received word, this means that the first detection bit C0 is erroneous.
A disadvantage of the Hamming code is that it cannot detect two errors.
Thus, if an error has occurred on bits X1 and X2, the obtained syndrome is equal to the sum modulo 2 of the syndromes corresponding to errors on X1 and X2, that is, to: S′″=(00101)+(00110)=(00011). The obtained syndrome indicates an error on bit X0, which is wrong.
Indeed, the Hamming code is known to have a minimum code distance d=3 and it is known that a linear code like the Hamming code is able to correct L errors and to detect L+1 errors if its minimum code distance d is strictly greater than 2L+1. Since d=3, L=0 and the Hamming code can only detect a single error with certainty.
Another disadvantage of the Hamming code is that the Hamming matrix is neither symmetrical nor regular. Indeed, it has been seen that syndromes with a single “1” are reserved to the control of the detection bits. Accordingly, these syndromes cannot be used to control the data bits and matrix H is constructed by using the remaining bit configurations. For the first column, the first possible configuration is (00011). For the second column, the next possible configuration is (00101), etc. Considering that the elements of a column correspond to the binary representation of a number, the variation of this number is not regular and includes jumps. Such jumps make difficult the forming of a circuit implementing the Hamming code as well as the syndrome decoding, that is, the determination of the erroneous bit.